/**
 * 你总共有n元，商人总共有三种商品，它们的价格分别是150元,250元,350元，三种商品的数量可以认为是无限多的，购买完商品以后需要将剩下的钱给商人作为小费，求最少需要给商人多少小费
 *
 * 样例
 * Example 1:
 * 	Input:  n = 900
 * 	Output:  0
 *
 * Example 2:
 * 	Input: 800
 * 	Output:  50
 *
 * @author jeymingwu
 * @date 2019/10/9 15:19
 */
public class L0801_Backpack_X {
    /**
     * @param n: the money you have
     * @return: the minimum money you have to give
     */
    public int backPackX(int n) {
        int[] v = {150, 250, 350};
//        int[][] dp = new int[v.length + 1][n + 1];
//        for (int i = 1; i <= v.length; ++i) {
//            for (int j = 0; j <= n; ++j) {
//                dp[i][j] = dp[i - 1][j];
//                if (j >= v[i - 1]) {
//                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - v[i - 1]] + v[i - 1]);
//                }
//            }
//        }
//        System.out.println(dp[v.length][n]);
//        return n - dp[v.length][n];

        int[] dp = new int[n + 1];
        for (int i = 0; i < v.length; ++i) {
            for (int j = v[i]; j <= n; ++j) {
                dp[j] = Math.max(dp[j], dp[j - v[i]] + v[i]);
            }
        }
        return n - dp[n];
    }

    public static void main(String[] args) {
        L0801_Backpack_X l0801 = new L0801_Backpack_X();
        System.out.println(l0801.backPackX(800));
    }
}
